The present invention relates to reconfigurable pipeline image processing systems and more particularly to processing systems utilizing arbitrary neighborhood window processing.
The binary neighborhood window processing capability of pipeline image processors is extended to handle arbitrary window functions, thereby enabling a greater variety of morphic structuring elements to be implemented in a single processing element. As a result, complete morphic algorithms are performed with fewer steps and hence, fewer processing elements.
In prior art systems, such as MITE (Morphic Image Transform Engine), only a certain class of image neighborhood windows were capable of being processed. The MITE system is described in "MITE: Morphic Image Transform Engine An Architecture for Reconfigurable Pipelines of Neighborhood Processors" by M. J. Kimmel et al, 1985 IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Management, Nov. 18-20, 1985, Miami Beach, Fla., and in patent application Ser. No. 06/759,640, filed July 26, 1985.
The MITE system is a reconfigurable arrangement of processing elements which process binary neighborhood window images concurrently in a parallel pipeline manner. Heretofore, neighborhood processors were generally limited to a neighborhood comprising a three pixel by three pixel square array of nearest neighbors. This limitation is particularly applicable in concurrent serial pipeline systems where speed and synchronization of the image processing is a foremost criteria.
In certain applications, a different neighborhood is preferable as a processing element in morphic processing. For example, to reduce an image to a smaller and smaller scale, the following approach may be used. The data is smoothed by taking an averaging or majority function over a two pixel by two pixel square window. The smoothed data is then processed by a window which uses every other pixel (for three pixels) in every other row (for three rows). One-fourth of the neighborhood transformations will be of no interest because of the previous smoothing processing, but every other pixel in every other row will be the result at half scale. The same sequence may be done iteratively, each iteration reducing the scale by a factor of two. With each iteration, the bits of interest will be reduced by a factor of four and the spatial relationship between pixels in the processing window will double in separation, hence requiring a different neighborhood or window each iteration.
Other image processing applications, including optical character recognition, use binary feature extraction which is related to neighborhood window processing, except that each feature or measurement sought usually requires a different set of input pels (window) to the process. Examples of different spatial relationships between bits of the feature (window) are shown in the article "The IBM 1975 Optical Page Reader Part III: Recognition Logic Development" by D. R. Andrews et al, IBM Journal of Research and Development, September, 1968, pp. 364-371. The described application can also require varying quantities of elements comprising the window.
In the past the generation of different windows has been achieved in several ways. Hardwired combinational logic implementation with shift registers which rotate the image for processing is an inflexible approach. Also, general purpose computers can simulate the extraction of this information. However, while such an arrangement is very flexible, it is also very slow. Neighborhood windows can also be implemented in special purpose image processing processors such as PRIME. The PRIME system is described in the article "PRIME -- A Processor Design for Character Recognition" by M. J. Kimmel, ACM SigMicro6 Preprint, Sept. 24-25, 1973, pp. 106-112.
Additional prior art relating to the PRIME system is found in U.S. Pat. Nos. 3,959,777 to Kimmel; 4,001,787 to Kimmel; and 4,011,547 to Kimmel. While the prior art approaches using a processor are quite general, it is also relatively slow and not well suited to serial synchronous reconfigurable pipeline processors. In these systems, each neighbor transformation or feature extraction takes a variable amount of time depending upon the complexity of the logic of the neighborhood function. This is so because the program running time is data dependent even though the parallelism of the PRIME system enables the neighborhood function to be calculated for more than one shift position at a time.
There are many other prior art pipeline image processing systems utilizing neighborhood transformations. Typical of the prior art is U.S. Pat. No. 4,395,700 to McCubbrey et al, in which a RAM serves as a recirculating line storage device for accommodating different raster scan line lengths in order to sufficiently access the neighborhood window for analysis. The described window is limited to a conventional M pixel by N pixel square array of neighbors.
Other known systems include neighborhood functions comprising other than nine pixels in a fixed spatial relationship. One such system known as the Golay hexagonal pattern transform is described in the article "Feature Extraction by Golay Hexagonal Pattern Transforms" by Kendall Preston, Jr. IEEE Transactions on Computers, Vol C-20, No. 9, September, 1971, pp. 1007-1014.